"""
链接：https://www.nowcoder.com/questionTerminal/2820ea076d144b30806e72de5e5d4bbf
来源：牛客网
已知一个背包最多能容纳物体的体积为V,现有n个物品，
第i个物品的体积为 vi, 重量为 wi
求当前背包最多能装多大重量的物品?

示例1
输入 10,2,[[1,3],[10,4]]
输出 4
第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4
"""


class Solution1:
    def knapsack(self, V, n, vw):
        # write code here
        res = 0
        dp = [[0 for _ in range(V + 1)] for _ in range(n)]
        for j in range(V):
            if vw[0][0] <= j:
                dp[0][j] = vw[0][1]
        for i in range(n):
            curBulk, curWeight = vw[i][0], vw[i][1]
            for j in range(1, V + 1):
                if curBulk > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - curBulk] + curWeight)
                    if dp[i][j] > res:
                        res = dp[i][j]
        print(dp)
        return res


# class Solution:
#     def knapsack(self, V, n, vw):
#         # dp是一个矩阵，行是考虑的物品数，分别是0，1，2； 列是背包的可用空间分别是0，1，2，。。。，10；
#         # 而对应位置的值就是给定条件下可以放的最大重量
#         dp = [[0 for _ in range(V + 1)] for _ in range(n + 1)]
#         # 这里给vw的index0插入了一个【0，0】是为了之后代码遍历方便点，这样index0 表示考虑0件物品
#         vw.insert(0, [0, 0])
#         # 对每一行进行遍历，注意，行的index就是代表考虑最近的index件物品
#         for row in range(1, n + 1):
#             for col in range(V + 1):
#                 if vw[row][0] > col:
#                     dp[row][col] = dp[row - 1][col]
#                 else:
#                     dp[row][col] = max(dp[row - 1][col], dp[row - 1][col - vw[row][0]] + vw[row][1])
#         return dp[n][V]


if __name__ == "__main__":
    A = Solution1()
    print(A.knapsack(10, 2, [[1, 3], [10, 4]]))
